The reliability of analog memory cells, such as Flash cells, typically deteriorates with usage. In some cases, however, it is possible to rejuvenate analog memory cells, e.g., by retaining them in a programmed state for a certain time period and/or by heating the memory cells. Rejuvenation techniques for analog memory cells are known in the art. For example, U.S. Pat. No. 8,248,831, whose disclosure is incorporated herein by reference describes a method for data storage in a memory that includes multiple analog memory cells fabricated using respective physical media. The method includes identifying a group of the memory cells whose physical media have deteriorated over time below a given storage quality level. A rejuvenation process, which causes the physical media of the memory cells in the group to meet the given storage quality level, is applied to the identified group. Data is stored in the rejuvenated group of the memory cells.